/*
 * EDF admission control on uniform processors
 * Assume the job execution time is measured on the reference machine 
 * having performance index 1.0.
 */

package jp.aist.gtrc.plus.admission.EDF;

import java.util.*;

import jp.aist.gtrc.plus.admission.*;
import jp.aist.gtrc.plus.admission.EDF.*;

public class EDFAdmissionUniform {
  
   private Schedule schedule;
   private List<Job> temporaryJobs;

   /*
    * getBestCPU() returns the earliest finished CPU considering 
    *  job ready time.
    */
   private UniformCPU getBestCPU(Job job, Collection<UniformCPU> cpus) {
      UniformCPU bestCPU = null;
      int bestCompletionTime = Integer.MAX_VALUE;

      for (UniformCPU cpu : cpus) {
          int t = Math.max(cpu.lastOccupied,job.readyTime) + (int) Math.ceil(job.exeTime/cpu.performanceIndex);         
          if (t < bestCompletionTime) {
             bestCompletionTime = t;
             bestCPU = cpu;
          }
      }
      return bestCPU;
   }

   /*
    * The cpu states may change after calling reserve(). Thus, be sure to 
    *  restore the original states. 
    * If newJobArray has numOfJobs == 0, no new job and just reschedule.
    * @return true if a valid schedule can be built for all jobs and the 
    *         schedule is changed accordingly.
    * In the future work, we can allow optimistic schedule in such a way that
    *   the invalidation of some admitted jobs having the deadline
    *   earlier than the incoming jobs are allowed (thus called optimistic
    *   schedule). Since the acceptance of the incoming jobs has no effect
    *   to such those jobs and  we hope that such jobs may luckily be 
    *   completed by the deadline.
    */
   public synchronized boolean buildSchedule(Collection<UniformCPU> cpus, Collection<Job> admittedJobs, JobArray newJobArray) {

      int id = admittedJobs.size();
      int firstNewJobId = id;
      ArrayList<Job> newJobs = new ArrayList<Job>();
      // create temporay jobs for incoming job array
      int submitTime = (int) (Calendar.getInstance().getTimeInMillis()/1000);

      for (int i=0; i < newJobArray.numOfJobs; i++) {
         Job job = new Job(id,newJobArray.name+"/"+i,newJobArray.exeTime,newJobArray.deadline,submitTime + AdmissionOperationManager.MAX_CONFIRMATION_TIME);
         newJobs.add(job);
         id++;
      }

      ArrayList<Job> sortedJobs = new ArrayList<Job>(admittedJobs);
      sortedJobs.addAll(newJobs);
      Collections.sort(sortedJobs, new DeadlineComparator());

      Schedule newSchedule = new Schedule();
      String plan = "";
      for (Job job : sortedJobs) {
         UniformCPU minCPU = getBestCPU(job,cpus);

//         System.out.println("EDFAdmissionUniform assigns job " + job.name + " to cpu " + minCPU.id + " at " + minCPU.lastOccupied);
//         int dispatch = minCPU.lastOccupied;
         int expectedStartTime = Math.max(minCPU.lastOccupied,job.readyTime);
         newSchedule.appendQueue(minCPU,job,expectedStartTime);

         minCPU.lastOccupied = expectedStartTime + (int) Math.ceil(job.exeTime/minCPU.performanceIndex); // execute job on this cpu
         if (minCPU.lastOccupied > job.deadline) {
            System.err.println("EDFAdmissionUniform fails to find a valid schedule since job " + job.name + " deadline " + job.deadline + " is violated. (to be completed at " + minCPU.lastOccupied + ")");
            if (job.id < firstNewJobId) {
               System.err.println("Scheduling condition fails and needs special administration. Further job submission is prohibited.");
            }
            if (newJobArray.numOfJobs != 0) { 
               return false; // new job fails to submit but delete job continues
            }
         /* // Optimistic Schedule 
//            if ( (job.id >= firstNewJobId) || (job.deadline > newJobArray.deadline) ) { // the incoming jobs or jobs having later deadline fails (optimistic schedule?)
               return false; 
            } */
 
         }
        
//         plan = plan + job.name +"("+minCPU.id+","+dispatch+"),";
      }
//      System.out.println("Plan: " + plan);
             
      this.schedule = newSchedule; // schedule changed only if a valid schedule is built
      this.temporaryJobs = newJobs;
      
      return true;
   }

   /*
    * return 0 if accepted, otherwise the recommended deadline.
    *
    * The cpu states may change after calling this method. Thus, be sure to restore
    *  the original states.
    * New schedule is returned. (Incoming jobs may have new deadline.)
    */
   public synchronized int buildScheduleAndRecommend(Collection<UniformCPU> cpus, Collection<Job> admittedJobs, JobArray newJobArray) throws AdmissionException {
      ArrayList<Job> admittedJobList = new ArrayList<Job>(admittedJobs);
      Collections.sort(admittedJobList, new DeadlineComparator()); // by deadline, then by id

      int id = admittedJobList.size();
      int firstNewJobId = id;
      int lastNewJobId = id;
      ArrayList<Job> newJobs = new ArrayList<Job>();
      int submitTime = (int) (Calendar.getInstance().getTimeInMillis()/1000);
      for (int i=0; i < newJobArray.numOfJobs; i++) {
           Job job = new Job(id,newJobArray.name+"/"+i,newJobArray.exeTime,newJobArray.deadline,submitTime + AdmissionOperationManager.MAX_CONFIRMATION_TIME); // use temporary job name
           newJobs.add(job);
           lastNewJobId = id;
           id++;  // id of each new job is incremental at the last id
      }
      ArrayList<Job> sortedJobs = new ArrayList<Job>(admittedJobList);
      insertAfter(sortedJobs,newJobs,newJobArray.deadline); // combine old and incoming jobs

      int newDeadline = newJobArray.deadline;
      Collection<UniformCPU> savedCPUs = null;
      int save_i = 0;
      boolean found = false; // if a schedule is found for all jobs including the incoming job array
      Schedule newSchedule = new Schedule();

      while (!(found) && (save_i <= admittedJobs.size())) {
         int i = 0;
         boolean isIncomingJobsScheduled = false;
        
         for (i=save_i; i < sortedJobs.size(); i++) {
            Job job = sortedJobs.get(i);
            if (job.id == firstNewJobId) {
               // do checkpointing 
               savedCPUs = cloneCPUs(cpus);
               newSchedule.checkpoint();
               save_i = i;
            }

            UniformCPU minCPU = getBestCPU(job,cpus);
            int expectedStartTime = Math.max(minCPU.lastOccupied,job.readyTime);
            newSchedule.appendQueue(minCPU,job,expectedStartTime);
            //System.out.println("Assign " + job.name + " on " + minCPU.id + " at exp. time " + expectedStartTime);

            minCPU.lastOccupied = expectedStartTime + (int) Math.ceil(job.exeTime/minCPU.performanceIndex); // execute job on this cpu
            if (job.id >= firstNewJobId) { // if this job belongs to the job array
               // find the completion time for the new job array
               if (minCPU.lastOccupied > newDeadline) {
                  newDeadline = minCPU.lastOccupied; 
               }
               if (job.id == lastNewJobId) isIncomingJobsScheduled = true;

            } else {
               if (minCPU.lastOccupied > job.deadline) {
                  System.out.println("EDFAdmissionUniform rejects new job since the deadline " + job.deadline + " of accepted job " + job.name + " is violated. (to be completed at " + minCPU.lastOccupied + ")");
                  if (!isIncomingJobsScheduled) {
                     System.err.println("Scheduling condition fails and needs special administration. Further job submission is prohibited.");
                     throw new AdmissionException("Invalid precondition in " + job.name + " since deadline is missed by " + (minCPU.lastOccupied - job.deadline) + " sec.");
                  }

                  /*
                   * trying to find the new completion time for the new job array
                   */
                  // re-insert new job array after the last violated jobs
                  sortedJobs = new ArrayList<Job>(admittedJobList);
                  insertAfter(sortedJobs,newJobs,job.deadline);
                  cpus = savedCPUs; // rollback last checkpoint
                  newSchedule.rollback();
//                  System.out.println("redo with new deadline " + job.deadline);
                  break; // redo testing again from the last checkpoint
               }
            }
   
//            System.out.println("put job " + job.id + " " + job.name + " on " + minCPU.id + " until " + minCPU.lastOccupied + " < " + job.deadline);
         }
         
         if (i == sortedJobs.size()) found = true;
      }

      this.schedule = newSchedule;  // The new schedule is found with user deadline or system recommended deadline .
      this.temporaryJobs = newJobs;

      if (newDeadline == newJobArray.deadline) {
         return 0;
      } else {
         //System.out.println("Recommended deadline = " + newDeadline);
         return newDeadline;
      }

   }

   /*
    * Assume newJobs is sorted by id.
    */
   private void insertAfter(ArrayList<Job> sortedJobs, ArrayList<Job> newJobs, int afterTime) {
      int position = sortedJobs.size();
      for (int i=0; i < sortedJobs.size(); i++) {
         Job job = sortedJobs.get(i);
         if (afterTime < job.deadline) {
            position = i;
            break;
         }
      }
//      System.out.println("Insert new jobs at position " + position);
      sortedJobs.addAll(position,newJobs);
   }

   private Collection<UniformCPU> cloneCPUs(Collection<UniformCPU> cpus) {
      Collection<UniformCPU> clone = new ArrayList<UniformCPU>();
      Iterator<UniformCPU> it = cpus.iterator();
      while (it.hasNext()) {
         UniformCPU cpu = it.next();
         //System.out.println("Checkpoint cpu " + cpu.id + " : " + cpu.lastOccupied);
         clone.add(new UniformCPU(cpu));
      }
      return clone;
   }

   public synchronized Schedule getSchedule() {
      return this.schedule;
   }

   public synchronized List<Job> getTemporaryJobs() {
      return this.temporaryJobs;
   }

}
